%%%%%% Ron, please rewrite the Section on Research methodology and plan in the proposal
%%%%%%%%%%   to include ideas from last year proposal, the ICTON paper and ICTON Presentation and the
%%%%%%%%%%   material you provided on traffic nonstationarity.
%%%%%%%%%%%% Last year material, the text you provided on traffic nonstationarity and the ICTON
%%%%%%%%%% paper are all copied into this document in Latex.
%%%%%%%%%%%%%  All the bibtex labels are consistent with those of GRF.bib
%%%%%%%%%%  This can be done by copy and paste in certain places.
%%%%%%% I made sure that the bibitems are consistent so copy and paste with the references will be ok.

%%%%%%%% Notice!!!
%%%%%  at least the words Objective 1 and 2 in the headings of last year:

%%%% 2. b. i. Optimized Traffic Engineering using Flow-size Dependent
%%%%% Routing(Objective 1)

%%%%% 2. b. ii. First Cut Comparison with existing Internet (Objective 2)
%%%%% should be modified (and some of the content also).

%%%%% are outdated.

%%%%% The reason is that the old first two objectives:

%%%%% I.      Define rigorously a flow-size dependent network optimization
%%%%% problem with cost and energy consumption as the objective and
%%%%% performance as the constraint.

%%%%% II.     Provide a first cut benchmarking method against OSPF based on cost.

%%%%% are no longer part of this proposal. They have been moved to the
%%%%% Internal grant for which the University offers me 180,000 HKD.

%%%%% If you like to see the internal grant application, please look in
%%%%% the folder "Internal grant" inside the folder GRF2011.

%%%%% The new objectives are in Section 1. I copy them here

%%%%% 1. Assume, at first, Poisson arrivals of heavy-tailed flows, develop
%%%%% and validate scalable and accurate simulation and analytical models
%%%%% to derive optimal dimensioning and routing. This will include
%%%%% optimal boundaries between the size-classes.

%%%%% 2. Extend objective 1 to a scenario of non-stationary traffic and
%%%%% provide optimal solutions that consider multi-hour traffic.

%%%%% 3. Benchmark the results of Objectives 1 and 2 against OSPF and
%%%%% quantitatively demonstrate the benefit of the new approach.

%%%%% 4. Demonstrate the robustness of the approach considering a wide
%%%%% range of networks and traffic scenarios.

%%%%% The section \section*{Traffic Nonstationarity and Multi-hour engineering} below can be used for Objective 2.

\newpage

such as IP at the access, and at much of the core, packet based
flows and shortest path routing

\section{Research methodology and plan - material from the last
proposal}

%%%%%%%%%%%%%%%%% RESEARCH METHODOLOGY %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Large \noindent \uline{\textbf{2. b. Research methodology and
plan}}

\normalsize \noindent
%%%%%%%%%%%%%%%%% OBJECTIVE 1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\textbf{2. b. i. Optimized Traffic Engineering using Flow-size Dependent Routing(Objective 1)}

A key objective in this project is to develop a new approach for Internet traffic engineering
that will be scalable and robust, and will have the potential to yield cost effective operation
 of the Internet. To achieve this objective, flow-size dependent routing is introduced in a
 form suitable for a large network such as the Internet. We choose this flow-size dependent
 routing to optimize cost, including energy cost, subject to simple but realistic performance
 constraints which are mandated in practice by ensuring that links have sufficient capacity.

Such an optimization problem is normally difficult especially given the size of the Internet
and the number of flows. However, by making pragmatic simplifications optimal solutions of
this model become easily characterized. They route flows on shortest paths - with path lengths,
as usual, the sum of link lengths. The novelty is that links are assigned different lengths
depending on the size of the flow. The first objective of this proposal is to rigorously state
and prove, under precise assumptions, the following result: If link cost is proportional to
mean offered traffic with a coefficient which depends on flow size, then flow-size dependent
shortest path routing is used in any optimal design. It is not claimed that this property
uniquely determines the optimal routing and capacity design. Simple examples exist in which
two designs of different cost which both satisfy this criterion. However, in the context of
the Internet it seems unlikely that shortest path routing will converge to a design significantly
less efficient than the optimal design. In the proposed routing architecture the processing
time involved in computing routing tables is expected to increase by a factor less than 3.

\noindent
\textbf{\textit{2. b. i. 1. Efficiency and Performance Considerations}}

Due to fluctuations in traffic demands, to provide quality of service, link capacity must
reflect the variance and potentially other traffic statistical characteristics (e.g. the
Pareto tail slope) as well as the mean, e.g. link capacity might be set to the mean plus
3 standard deviations of the traffic, measured over, for example, one second. Furthermore,
the additional bandwidth required to support an additional flow depends very strikingly
on the current traffic mix on the link. This is why traffic aggregation is so beneficial
to performance provision and cost reduction.

The standard deviation to mean ratio of long flows is much higher than for short flows.
Large flows can potentially contribute 1\% to aggregate mean traffic on the link, but
50\% or more to the aggregate standard deviation. Large flows have this potential for
disproportionate contribution to variance because the variance of the total bytes in
the entire length of the large flows arriving in a given interval is infinite. Moreover,
if a flow is moved from one link to another, its contribution to the variance of the
total traffic on the link changes very significantly. Therefore, individual large flows
should be routed so that they preferentially use large pipes with more traffic, to
reduce their own contribution to the variance - not necessarily the shortest path in
the usual sense. In the optimization, we explicitly account for the contribution to
link cost due to the larger standard deviation of larger flows. Furthermore, when an
identifiable large flow emerges it can be allocated exclusive and sufficient shared
network resources to carry its load without disrupting the remaining traffic. This
guarantees its performance and protects others from its impact.

\noindent
\textbf{\textit{2. b. i. 2. Energy Considerations}}

The traffic dependent activities which require energy in networks are: (i) flow set-up
and termination, (ii) packet routing and forwarding, (iii) transmission and signal
regeneration. Flow routing (virtual paths or circuits) uses more energy than IP routing
in flow set-up and termination (i), but saves energy in (ii) because the use of labels
or a hash table for packet forwarding is more energy efficient than packet-by-packet
routing using look-up tables at the router. Since for mice the set up cost per bit (i)
is most significant relative to the other cost components, they are likely to compromise
on (ii) and (iii) and choose permanent perhaps longer paths than the larger flows.

\noindent
\textbf{\textit{2. b. i. 3. Other Costs}}

In addition to the energy cost, we will also consider other operational expenditure
(OPEX) cost and capital expenditure (CAPEX) cost. (See relevant work done by the PI
in \cite{Parthiban2009}.)

\noindent
\textbf{\textit{2. b. i. 4. Optimization}}

Assuming that cost is a function of the total investment in switching (in the broadest
sense) and transmission equipment, together with the use of switching and transmission
(in the broadest sense) and that we wish to constrain our design choices to achieve a
loss level of 1\% (for example) on all links, we take cost to be a linear function of
the form $\sum \int C_{k,s}\mu_{k,s} ds$, where $C_{k,s}$ is the cost per flow for flows
of length s through link k and $\mu_{k,s}$ is the intensity of flows of length s on link k.
If the cost coefficients are independent of path flows (which is true in a local sense,
i.e. in the vicinity of a certain design), the optimal solution to this probl
em, i.e. the optimal routing and link capacity allocation, will choose, for each flow,
the path with the minimum value for $\sum C_{k,s}$, i.e the minimal flow-size dependent
path length.

Optimal set-up and tear-down of permanent or semi-permanent virtual paths can be set
using known techniques \cite{Chlamtac1994,Saniee2000,He2008} based on their
traffic load. Links which cannot be used without incurring an additional setup cost
whenever they are used -- because the link is actually a notional LSP, or WDM routed
wavelength, for example -- can be seamlessly included in our model of a network. The
additional computational complexity of including these "virtual links" as options for
routing is linear in the total number of links per node, because this is the complexity
of the shortest path algorithm used in routers.

As a consequence of this routing strategy, mice will use existing paths to avoid
significant set up cost (i), and reduce switching cost (ii); elephants on the other
hand will often choose a path set up on a one-off basis because setup cost is not
significant relative to the other costs they incur, and using a specially configured
path will save switching cost. The impact of the variance of elephants will be
minimized by using links from an aggregate of dynamically allocatable bandwidth,
e.g. LSP's or-$\lambda$ SP's. The kangaroos that use IP will avoid paths with high
setup cost and will choose the shortest path in terms of hops to reduce their
significant routing and transmission cost. The classification to the various types
will occur naturally by using flow-size dependent routing tables. Identifying the
class of flow to which a packet belongs is a subject with its own extensive literature
and is not considered in this project.

\noindent
%%%%%%%%%%%%%%%%% OBJECTIVE 2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\textbf{2. b. ii. First Cut Comparison with existing Internet (Objective 2)}

If traffic is routed on shortest paths, and decentralized management of links ensures
that they have adequate capacity, the emergent design will be in a certain sense
approximately optimal. In this project we improve on this concept in a practical way
by adopting flow-size dependent routing and queueing. Because flow sizes are heavy-tailed,
satisfactory estimates of flow sizes can be obtained in a scalable manner (to the
extent needed). For the same reason, we can dynamically estimate the variance contributed
by each flow, which is why the improvement in network cost - for a given performance
level - which can be achieved by allowing routing to depend on flow-size, is highly
significant. We will estimate this improvement by comparing the cost of two networks
carrying the same traffic, and with identical topologies (see Figure 2), where
capacities in both cases are selected using a simple mean plus two (or three) standard
deviations rule. A more complex comparison will also be made - with more practical link
capacity strategies, once the simplistic case has been completed. This is discussed in
the next section.

\noindent
%%%%%%%%%%%%%%%%% OBJECTIVES # & 4 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\textbf{2. b. iii. Performance evaluation and benchmarking (Objectives 3 and 4)}

\noindent
\textbf{\textit{2. b. iii. 1.Analytical approach}}

A fixed-point algorithm will be used to model the autonomous process of traffic being
routed on flow-size dependent shortest paths in the Internet, with capacity upgrades
as needed according to measured throughput and congestion on links. The iteration
proceeds by (i) assuming a certain set of flow-size dependent routing tables and then
computing, the mean and variance of traffic on each link by adding up the mean and
variances of the flows which share this link, and then computing the appropriate
capacity, by the mean + 2 (or 3) sigma rule, in order to achieve the planned loss
rate on each link; then (ii) given the capacity, mean and variance of traffic on each
link, computing the flow-size dependent routing tables for each router. The steps (i)
and (ii) are repeated until the link capacities computed at each iteration are unchanged.

In order to focus on the essential difference between flow-size dependent routing and
conventional shortest path routing we will, in the first instance, allow link capacities
to be set at arbitrary values (i.e. not constrained to specific capacities) and assume
that they are managed continuously to have precisely the capacity mean + 2 (and alternatively 3)
standard deviations. This assumption will be adopted, for both the flow-size dependent
routed case, and the conventional routed network. This allows the two approaches to be
compared on the basis that both networks deliver similar performance, and it is therefore
fair to assess the advantages of the flow-size dependent routing concept by simply comparing
cost.

We then propose to investigate the following problems: \textit{What level of performance
will result for each separate flow category? How does this vary depending on whether
Fair Queueing (FQ) or Largest Flow Last (LFL) is used as the queue algorithm at the head
of each link? Is LFL necessary for satisfactory use of flow-size dependent routing? How
significant are the performance advantages gained from flow-size dependent routing? Does
this depend on whether FQ or LFL is used in queueing.}

Building on \cite{Addie2007} and the work in GRF 124709
on single queues, we will extend the work here to evaluate end-to-end network wide performance.
We propose to investigate, by formulating and solving partial differential equations for
network state: (i) LFL and FQ as queue disciplines for each link; and for routing, (ii)
largest flows (elephants) use one-off tunnels (either MPLS or GMPLS tunnels), (iii) shortest
flows (mice) use permanent tunnels, and (iv) flow-size dependent routing in general. If the
flow management protocol ensures moderately better treatment for shorter flows than for
longer ones, it is possible to establish, and solve, equations for the stationary probability
distribution of flows shorter than a certain length in terms of the stationary probability
distribution of flows shorter than another infinitesimally shorter length. On the other hand,
if all flows are treated identically, as in FQ, the impact of short flows on long flows can
be replaced by their mean impact with very little error. In this case as well we can solve for
the stationary distribution of the network state. This method of analysis applies equally well
to both flow-size dependent shortest path routing, and conventional shortest path routing,
since the latter is a special case of the former. We can therefore analyse networks designed
in both ways and make the necessary comparisons to achieve the proposed benchmarking. A
reference manual for techniques needed in analysing Poisson-Pareto-like processes will be
developed as a basic tool for use in undertaking this analysis work.

\noindent
\textbf{2. b. iii. 2. Simulation}

Simulation is an essential technique for analysis of the performance of communication systems.
Simulation of systems with heavy-tailed flows is fundamentally difficult, not to say impossible,
when the degree of heaviness of the tails of flow size distributions becomes extreme, unless a
special simulation technique is adopted. Fortunately such a method has been developed by Co-I
Addie \cite{Addie2008,Addie2009a}. This technique is similar to hybrid simulation but
with the significant difference that the simulation of flows of different lengths is undertaken
over different simulation durations. In particular, a simulation does not have a unique length.
Long flows see a long simulation, and short flows see a short one. Observations are made only
when the details necessary for them to be accurately represented are present. This simulation
method is at an early stage of development and consequently each new application requires
innovative software development. We intend to publish a guide on the simulation technique
which will improve the appreciation of these methods and facilitate newcomers to learn how to
use the method more easily.
The network of \cite{Maxemchuk2005} (see Figure 2) will be used to provide an example network.
The traffic on this network will be assumed to follow a Poisson-Pareto burst model. A mixture
of flows which seek to affect their desired transfer of bytes as quickly as the network will
allow, and others which do not seek to exceed a preset rate will be included.

\textbf{2. b. iv. Plan}

A list of the tasks, with estimates of duration, resourcing, and pre-requisite tasks, is given
in Table 1. These tasks will be carried out in parallel to the extent allowed by their
dependencies, which are shown in the table. Except for writing the snapshot simulation guide
and the development of a guide for analysis of Poisson-Pareto like processes, the tasks of
writing and publishing the results are implied and associated with most of the tasks and they
are not explicitly mentioned for brevity. In addition to the time spent by the SRA and RA,
indicated in the table, the PI and the Co-I will be heavily involved in the project as described
in Part II.8.

\newpage

\section*{Traffic Nonstationarity and Multi-hour optimization}

It is well known that Internet traffic exhibit nonstationarity
\cite{Karagiannis2004,Cao2001}. We plan to extend the work to
include a scenario where the parameters of the arrival process
slowly evolve. A network design that aims to optimize routing of
such traffic is known as multi-hour optimization
\cite{Maxemchuk2005} and it is a good application of the method in
this proposal. The proposal includes dynamically routed flows and
virtually-permanent links which are routed according to the current
costs of the network, and which may slowly evolve. These mechanisms
should be very effective in addressing the slow changes in traffic
(non-stationarity) which are a fact of life in real networks.

But how can we expect a good multi-hour network design to emerge
from a philosophy in which routing is flow-size dependent, and
follows shortest paths according to flow-size dependent costs, and
which is not explicitly traffic-dependent?

Here is how our proposed scheme should provide effective multi-hour
engineered design: Although routing is not traffic-dependent, as
traffic changes, link costs will change, marginal costs of certain
virtual paths will change, and cost of use of dynamically routed
links will change, leading to some virtual paths being introduced,
and others being withdrawn, and to some dynamic routes being used
more often, and others less often.

This interpretation of the proposed design methodology relies on an
extension which has not been contemplated up to now, which is that
as well as an iterative scheme leading to a single optimal design,
additional iterations with modified traffic (traffic for different
times of the day or year) will need to be undertaken. When an
adequate number of different configurations of traffic have been
considered in this way, the overall design, for all hours of the
day, or year, can be deduced from the configurations for each
specific hour.

\newpage

%%%%%%%%%%%% ICTON %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{THE ICTON2010 PAPER: Optimizing Multi-Layered Networks
Towards a Transparently Optical Internet}

\section{Introduction}

\noindent The currently evolved Internet architecture is based on a
variety of technologies and serves numerous services and traffic
types. Internet design that will minimize cost subject to meeting
quality of service (QoS) requirements of the various services
requires simultaneous optimization of many aspects, such as,
technology choices, virtual topology, routing, and traffic grooming.
It is clear that optimizing the entire Internet from all these
aspects is too difficult given its size, the multiple domains, the
wide range of technology options and the unpredictable and complex
nature of the traffic.

\noindent There are many papers which propose mathematical
programming formulations for network design (e.g.
\cite{Ramaswami1996}) however these are applicable only to small
networks and only consider a subset of the above problems. This
limitation is also applicable to certain heuristics that have been
proposed (e.g. \cite{Zhu2002,Sridharan2002}), that are not scalable
to large problems. Furthermore, when a large number of technologies
are considered simultaneously, formulation of the design problem as
a mathematical program is a task of massive complexity, and its
solution, if it can be obtained, cannot be intuitively understood.



One relevant contribution is the development of the generic graph
model \cite{Zhu2003} that allows for a multilayer optimization of
WDM network. This work provides a foundation for WDM network
optimization in a scalable way.


The book \cite{Zhu2005} adopts a formulation of the network design
problem in terms of a problem of optimal routing through a
multi-layered network (or a multi-layered graph). This is quite
similar to our approach. However, our objective includes technology
choices, and link capacity dimensioning as part of the problem,
whereas \cite{Zhu2005} assumes that the link capacities are given,
and a specific collection of grooming technologies is available, so
the task to be solved is how to route traffic through this network.
Also, we consider a statistical model of traffic adopting a Pareto
distribution for flows, whereas \cite{Zhu2005} analyses a scenario
rather than a statistical model.

\subsection{A Unified Layered Routing Model}

\noindent In this paper we propose and develop a unified framework
for multiple technologies that interwork together under realistic
assumptions of traffic demands. To do this we adopt a model based on
the following principles: (i) each layer is associated with a unique
technology (e.g. IP, ATM, WDM, or a specific grooming technique);
(ii) traffic can be modelled as a Poisson stream of independently
distributed\textit{ flows}; and (iii) each flow is routed on the
least-cost path\textit{ for this flow size} in each layer
(technology). Each layer provides the ``service'' of passing a
request from the layer above directly to the layer below. Sometimes
this is the cheapest way to fulfil a service request. Hence,
adopting least-cost paths in each layer ensures that the least-cost
technology will be used.

\noindent A new technology can be incorporated into this model by
choosing a collection of parameters which determine, for each layer,
what it will cost to deliver a certain type of traffic and how
traffic will be {\em split} between layers when there is a choice.
Each layer is a network in its own right, and the links of layer
$n+{\rm 1}$ correspond to the traffic streams of layer $n$. We then
use shortest-path routing as the design principle for each layer, so
the design of each layer is {\em almost} independent from the design
of other layers.

\noindent However, since the cost of links in layer $n+{\rm 1}$ is
determined by the cost of the whole path that these links follow, in
layer $n$, the traffic in layer $n+{\rm 1}$ will change with the
costs in layer $n$, and this will cause the traffic in layer $n$ to
change and hence the costs in layer $n$ will change again. An
iterative repeat substitution scheme for designing all the layers
converges quickly, in our experiments, although the experiments are
at an early stage.

\subsection{Layered Routing}

\noindent We assume that all nodes are {\em capable} of the
switching and routing of all the layers, i.e. each node is equipped
with all technologies. Physical transmission occurs only at layer 0.
Links at higher layers are composed of paths through the layer
beneath. Any path, between any pair of nodes in layer $k$, is a
possible link in layer $n>k$, however in many cases it will
transpire (for reasons of cost) that a given pair is not connected.
Every layer provides, as a bare minimum, the service of merely
providing access to the links of the layer below, at no extra cost.
If this is the only function provided in a certain layer after the
optimization algorithm has completed its work, this means that it
has been determined that the technology corresponding to this layer
is not cost effective and will not be used. For example, due to the
excessive cost of handling individual packets in the IP layer
\cite{Roberts2009}, it might be more cost effective to delegate
switching (possibly optical switching) to lower layers under a given
future cost structure.

\subsection{Cost of Communication and Flows}

\noindent Internet cost can be classified into three categories:

\begin{enumerate} \item  Data processing: in the IP layer this
category includes costs of equipment, maintenance and energy
associated with individual packet processing in routers (including
repeated buffering and routing-table look-up) which is energy
inefficient \cite{Roberts2009} especially for large flows. In lower
layers these will include for example cost of add-drop multiplexers
(ADMs).

\item  Connection set-up, including recording and updating hash
tables in flow-based routing, or the setup cost for an SDH or WDM
paths in cases where those are used.

\item  Transmission: In line with these three categories, we
distinguish three size-based flow types:

\item  Mice: these are the small flows for which any flow setup cost
will be more significant than any per-packet or per-byte costs.
Their number is large and it may be optimal to route them in pre-set
existing tunnels - possibly a lightpath. Their tunnels may be longer
than shortest path (similar to busses that drop off and take up
passengers along their routes).

\item  Elephants: these are large flows for which the flow setup
cost will be insignificant. Their numbers are relatively small, so
they justify complex flow setup and clear-down, possibly including
the setup of a routed wavelength. Individual packet processing is
avoided.

\item  Kangaroos: they are flows that are larger than the mice and
smaller than the elephants where the connection set-up cost is
neither negligible nor significantly larger than their data
processing cost. It may be beneficial to route them based on the
current IP architecture and to use shortest-hop-path routing to
minimize the number of hops for them because their packets are
treated individually at every router. \end{enumerate}

\noindent The best choice of boundaries between these flow-sizes,
and also the best number of different sizes which should be
distinguished has not yet been determined and will be the subject of
investigation.

% \iflong
% \input{costtests.tex}
% \fi


\section{THE TRAFFIC MODEL} \label{traffic}

\noindent Assume that the arrival process of the flows follow a
Poisson process and that the sizes of the original flows are
independent and Pareto distributed. As we assigned flows to layers
based on their size, flow sizes in a given layer may follow a
truncated Poisson distribution.

\noindent

\subsection{Flow Size Distribution}\label{truncpareto}

\noindent We assume that traffic in each layer is either continuous
at a fixed rate, or is made up of a Poisson stream of flows, of rate
$\lambda $, which have a truncated (or untruncated) Pareto
distribution with shape parameter $\gamma $, with minimum size
$\delta $ and maximum size $\Delta $. (We allow for $\Delta $ to be
arbitrarily large ($\Delta =\infty $) so the case of untruncated
Pareto distribution is included.) Assuming that flow sizes are
measured in bits, the probability that a randomly selected flow is
shorter than $t$ is:

\begin{equation} \label{truncparetoprob} \left\{\begin{array}{ccc}
{0,\quad \quad \quad \quad \; \; } & {} & {t<\delta ,\quad \quad }
\\ {\frac{\left({\tfrac{\Delta }{\delta }} \right)^{-\gamma }
-\left({\tfrac{t}{\delta }} \right)^{-\gamma }
}{1-\left({\tfrac{\Delta }{\delta }} \right)^{-\gamma } } ,} & {} &
{\delta <t<\Delta ,\; \; } \\ {1,\quad \quad \quad \quad \quad } &
{} & {t\ge \Delta .\quad \quad } \end{array}\right. \end{equation}
The mean bit-rate of such a Poisson stream of flows is:

\begin{equation} \label{truncparetorate} \frac{\lambda \gamma
\left(\delta ^{{\rm 1}-\gamma } -\Delta ^{{\rm 1}-\gamma }
\right)}{(\gamma -{\rm 1})\left(\delta ^{-\gamma } -\Delta ^{-\gamma
} \right)} {\rm .} \end{equation}

\section{FIXED-POINT ALGORITHM FOR LINK CAPACITY ASSIGNMENT}

\noindent A simple and effective way to evaluate the performance of
telecommunications networks is to use an approach involving {\em
fixed point iterations}. The behavior of traffic is affected by the
capacity of the links, switches, and routers that it passes through,
and also by the other traffic that uses the same resources at the
same time. Given all the conditions which apply, relatively simple
models can be used to predict the performance and behavior of one
traffic stream. A fixed-point algorithm can then be used to predict
the behavior and performance of the complete collection of traffic
streams which share a network by successively replacing the traffic
streams by streams which exhibit their behavior in the presence of
the other traffic.

\noindent Fixed-point algorithms have been used extensively in
performance evaluation of telecommunications network. One example is
the so-called Erlang fixed-point approximation (EFPA) method. It is
based on decoupling the given system into independent server groups
(subsystems) and computing blocking probability for each subsystem
independently. EFPA was first proposed in \cite{Cooper1964} in 1964
for the analysis of circuit-switched networks and has been
extensively used since then in network analyzes and design. See for
example, \cite{Rosberg2003} and references therein.

\noindent In this paper our objective is not to estimate blocking
probabilities but instead to estimate required capacities.
Therefore, instead of iterating until convergence of loss
probabilities has occurred, we adjust capacities at each iteration,
and continue iterating until capacities have converged. Identifying
conditions which ensure convergence is beyond the scope of this
paper. Whereas in the EFPA the Erlang B formula is used to estimate
loss, in the fixed-point iteration presented here simple formulae
(e.g., mean traffic plus three standard deviations of traffic) are
used to estimate the capacity required to achieve a certain target
for loss on each link.

\noindent Alternative approaches are used for link dimensioning
based on the following link classifications:

\begin{enumerate} \item  Links which carry only traffic representing
permanent virtual links of a specified capacity (constant bitrate or
peak rate allocated). There the required capacity is obtained by
simply summing up the required capacities and rounding up to the
next module size.

\item  Links where traffic is statistically random, but they are not
the bottleneck for any of the streams that pass through them. Such
links are typically located in the core network and their streams
are bottlenecked typically at the access. For them, the required
capacity is the mean traffic plus three standard deviations. The
traffic variance is estimated by adopting a Poisson model for the
number of active flows, in which the {\em rate} exhibited by each
flow is assumed to be the rate of the \textit {maximin link} feeding
traffic into this link, i.e. the maximum over all the traffic
streams, of the speed of the bottleneck link for that traffic
stream. If this maximin rate is denoted by $r_{mm} $, and the rate
of the link is $r_{L} $, the variance of the rate on the link -
using a Poisson model -- is approximated by $r_{mm}^{2} \left(r_{L}
/r_{mm} \right)=r_{mm} r_{L} $.

\item  For each one of the remaining links, some traffic streams
experience the link as their bottleneck link. Such links are
typically located in the access network. The link behavior is
governed by fair queueing, and therefore we adopt for them a
utilisation target (which may be different in each layer).
\end{enumerate}

% \iflong
% \input{dimtests.tex}
% \fi

\section{ANALYSIS OF LAYERED NETWORKS} \label{layeredfpoint}

\noindent The basic fixed-point algorithm described in the previous
section can be extended to layered networks so long as we have a
scheme for splitting traffic between layers. Splitting the type of
traffic described in Section 2 is straightforward so long as the
only criterion used for deciding which way to direct traffic is flow
size.

\subsection{Layered Architecture}

\noindent The most important principle of layered network
architecture is that {\em each layer of a network employs services
provided by layers below to provide services to the layers above}.
Sitting on top of this layer-cake of services are the demands from
the users, which we refer to in this paper as {\em traffic streams}.
Traffic from these user-generated traffic streams is carried by
assigning it to {\em paths} through the layer at the top. When there
is a layer below this top layer, it is employed for one and only one
reason: to implement links at the top layer. There are three
distinct ways in which layer $n$ can implement a link between node
{\em A} and node {\em B} at layer $n+{\rm 1}$:

\begin{enumerate} \item  layer $n$ already has a link between {\em
A} and {\em B} (either because \textit{n} = 0, and there is a
physical link between {\em A} and {\em B}, or n$>$0 but layer n-1
has a link between {\em A} and {\em B}) and it simply passes on this
service, at no {\em extra} charge (beyond transmission cost), to the
layer above; when a link from {\em A} to {\em B} already exists, and
is not over-utilized, this will always the best way to provide the
link from {\em A} to {\em B} at layer $n+{\rm 1}$.

\item  layer $n$ does not have a link from {\em A} to {\em B} but it
has a path from {\em A} to {\em B} which it can permanently package
as a link, for layer $n+{\rm 1}$ (e.g. a lightpath at the optical
layer can be viewed as a link at the IP layer).

\item  layer $n$ does not have a link from {\em A} to {\em B} but it
can dynamically set up, as required, a path through its network from
{\em A} to {\em B}. \end{enumerate}

\noindent There is usually a significant extra cost in making use of
links as in Cases 2 and 3. In Case 2, this cost is mainly due to the
fact that modularity requirements in layer $n$ will mean that the
capacity of the path set up through this layer might be considerably
more than is actually needed. In Case 3 the cost is due to the fact
that every time a layer $n+{\rm 1}$ is set up, a significant cost is
incurred. Modularity always restricts the use of paths through layer
$n$, however in Case 3 we can assume that the path is fully utilized
while the link is in use, so we can neglect this cost in Case 3.
Since all the traffic carried by layer $n$ is derived from one of
these three mechanisms, the traffic streams in layer $n$ correspond
one-to-one with the links in layer $n+{\rm 1}$.

\subsection{Splitting }\label{splitting}

\noindent Suppose the arrival rate of flows in a traffic stream is
$\lambda $ with a range of flow sizes from $\delta $ to $\Delta $,
and this is split on the basis of whether a flow is bigger or
smaller than $D$. If the arrival rate of flows less than size $D$ is
$\lambda _{{\rm 1}} $, then the stream containing these smaller
flows will have the standard model, but with rate $\lambda _{{\rm
1}} $, and flows in the range $\delta $ to $D$.while the other
stream will have a rate$\lambda -\lambda _{{\rm 1}} $ and a range
flow sizes from $D$ to $\Delta $.

\subsection{Merging}

\noindent The parameters of a merged stream that we need to choose
are: (i) the flow arrival rate; (ii) the minimal flow size $\delta
$; and (iii) the maximum flow size $\Delta $. (We assume that all
traffic exhibits a common power law, with exponent $\gamma $.)  In
order to determine the parameters of a merged traffic stream we
adopt the principle that the flow rate of the merged stream should
be the sum of the flow rates of the component streams, the maximum
flow size should be the maximum of the maximum flow sizes of the
component streams, and the mean bit-rate of the merged stream should
be the sum of the bit-rates of the component streams. It follows
that we have one free parameter, the minimum flow size, with which
to ensure that the mean bit-rate is correctly matched. Since the
mean of a Poisson stream of truncated (or untruncated) Pareto flows
is given by \eqref{truncparetorate}, if the mean rate of such a
traffic stream is m, the $\delta $ required to match this is the
solution of:

\[m=\frac{\lambda \gamma \left(\delta ^{{\rm 1}-\gamma } -\Delta
^{{\rm 1}-\gamma } \right)}{(\gamma -{\rm 1})\left(\delta ^{-\gamma
} -\Delta ^{-\gamma } \right)} {\rm .}\] Rearranging this gives:

\[\delta =\frac{m(\gamma -{\rm 1})\left({\rm 1}-(\Delta /\delta
)^{-\gamma } \right)}{\lambda \gamma ({\rm 1}-(\Delta /\delta
)^{{\rm 1}-\gamma } )} ,\] which can be used repeatedly to solve for
$\delta $.


\section{IMPLEMENTATION}

\noindent An algorithm for network design of a layered network was
described and this algorithm has been implemented (see
\cite{Zareer2004,Addie2006,Addie2010}) and some preliminary
experiments carried out. The experiments confirm that the network
design algorithm converges quickly for very large networks.

\noindent \textbf{}

\section{CONCLUSION}

\noindent We have outlined a unified optimization framework for a
multi-layer network that facilitates choice of technologies, link
dimensioning and design of virtual topology. More details on the
software that is being developed and implementations for specific
scenarios are available in \cite{Zareer2004,Addie2006,Addie2010}.

\newpage

%%%%%%%%%%%%%%%%%% ICTON SLIDES %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{INCTON2010 Presentation - relevant slides}

\subsection*{A free choice model}

We consider a model where every flow/service chooses the route and
technology best for it. After the intuition motivates the model, we
forget all intuitive arguments and let the math talk. No foregone
conclusion, no bias, no prejudice. However, this is still only a
philosophy because \begin{itemize} \item inputting the costs is not
trivial, \item  assumptions are made for tractability. \end{itemize}

If realistic costs and topology are used and mostly all-optical
choices are made, we are getting closer to a Transparent Optical
Internet.

\subsection*{The Traffic model}

The traffic for each end-to-end demand follows  a Poisson Pareto
burst process (PPBP) - Poisson arrival process of Pareto distributed
bursts/flows.

\subsection*{Flow size distribution}

Truncated Pareto

\subsection*{Formula for Mean Bitrate}

\subsection*{The Approach}

\begin{itemize}

\item Layers � each layer - a technology (e.g. IP, ATM, WDM)

\item Traffic model: Poisson arrivals of flows

\item Each flow � Pareto distributed size

\item In principle, each flow is routed on the least-cost path for
this flow size in each layer (technology).

\item Lower layer costs less per bit � but modules are larger.

\item Some intuition: Flocking � so relatively not many large links.
High utilization of link and hibernation of unused links. Elephants
decide the permanent path and mice use the scraps.

\item  A new technology can be incorporated into this model by
choosing a collection of cost parameters for traffic delivery.

\item  Traffic stream is split between layers according to flow
sizes.

\item  Traffic stream is split between alternative routes according
to flow sizes.

\item The traffic is consistent in routing � the mean is maintained
consistent � no traffic is lost � or added.

\item For simplicity and scalability merging of many Pareto models
is modeled by a single Pareto model. (Peak and mean are fitted �
lower bound is adjusted.)

\item Fixed-point iterations are used to obtain the capacity
required for each layer.

\item The convergence criterion is the sum of the required capacity
differences between two consecutive iterations (absolute values) of
each link/layer < small value.

\item For simplicity and scalability, merging of many Pareto models
is modeled by a single Pareto model. (Peak and mean are fitted �
lower bound is adjusted.)

\end{itemize}

\subsection*{Conclusion} \begin{itemize} \item Power usage and
related cost is an important consideration. \item We have provided a
scalable flow-size based traffic engineering for link dimensioning
and technology choices. \item It can motivate transparent Internet
when the cost structure is right. \end{itemize} \newpage

\section*{Additional References}

\subsection*{Papers cited in the ICTON2010 paper \cite{Addie2010a}}

\cite{Ramaswami1996,Zhu2002,Sridharan2002,Zhu2005,Cooper1964,Zareer2004,Addie2006,Addie2010}

\subsection*{Green Internet}

\cite{Tucker2010,Green2010,Baliga2010,Weichenberg2009,Baldi2009}

\newpage

\section*{Reviewers' Comments}

\subsection*{Reviewer 1}

{\bf Please comment on the objective(s) of the proposal. Could the
research agenda address the objective(s)?}

\vspace{0.5 cm}

Grade: Very Good

\vspace{0.5 cm}

The proposal aims to provide a flow-size dependent routing framework
for current Internet traffic, and show via analysis and simulation
that this framework will lead to energy efficiency. While the fact
the flow-state routing will lead to energy efficiency is well-known,
the PIs want to evaluate this from the perspective of flow-sizes,
which is slightly different, as well as look at connection setup
costs. This is a very good objective and will be useful as well.

\vspace{0.5 cm}

{\bf Please comment on the Research Design and Methodology.}

\vspace{0.5 cm}

Grade: Very Good

\vspace{0.5 cm}

The brief synopsis is that the research is well planned, albeit too
long. The PIs have designed the program to last 36 months, with
various amounts of time spent for designing, analyzing, evaluating,
simulating and comparing the various parts of this proposal.  The
methodology is very sound, and in fact desirable, since the PIs hope
to show the theoretical validity of their framework by showing the
optimality of the flow-size dependent routing, before depending on
the simulations to verify the same.

\vspace{0.5 cm}

{\bf Please comment on the feasibility
 of the proposed research. Why?}

 \vspace{0.5 cm}

 Grade: Excellent

  \vspace{0.5 cm}

 The proposed research activity is entirely feasible, and consists primarily of
 mathematical modeling and analysis at the beginning, followed by comparative studies
 via simulation. It can be easily accomplished within a 2-year window, and especially
 within time and budget if you have both an RA and a SRA.

   \vspace{0.5 cm}

 {\bf What do you consider to be the most original or innovative aspect
 of the proposed research? What advances will the research result bring
about to the related field if the proposed research is successful?}

   \vspace{0.5 cm}

   The most innovative aspect of this proposal is the flow-size dependent routing,
   and the use of fixed (possibly) long-hop paths for routing short-lived flows.
   It would increase the pressure on router vendors to implement such functions since it will
   demonstrate the viability of such a model in the current Internet.

   \vspace{0.5 cm}

   {\bf Please comment on the reasonableness
 of the proposed budget and manpower planning }

    \vspace{0.5 cm}

    The duration of 36 months is at least 1 year more than what is needed for the proposed project.
    Looking at the timeline of the proposed work, it looks like the bulk of the time
    is proposed for the simulations (12+18 man-months = 30 man-months).
    While the idea of comprehensive simulation is good, the simulation part of the work, as outlined,
    will not take more than 6 man-months. It is not clear why the PIs request more than 30 man-months
    for this component. It is simply not needed, if the PIs are willing to use publicly available
    tools such as NS-2, etc. for the RA/SRA to build upon. This would be the recommended course of action as well.

Having said that, combining a RA and SRA in this activity would be
beneficial to odds of overall success for this project.

  {\bf Overall Comment:}

  \vspace{0.5 cm}

  {\bf Strength:}

The proposal is a very solid proposal that focuses on a emerging
problem in core networks, i.e., how to engineer energy efficient
routing in networks. The PIs use flow-sizes as a metric to devise
routes, and aim to combine this with the flow-based routing model to
achieve better overall savings in the network. This is a nice idea,
and if carried to its successful conclusion, has a good chance of
attracting quite a lot of positive attention. The PIs have a good
track record in the past of studying such problems, and are likely
to succeed here as well.

  \vspace{0.5 cm}

{\bf Weaknesses:}

 An interesting question would be how to identify
the mice, elephants and kangaroos, and this reviewer believes that
it should have been addressed in this proposal as well. The second
weakness is the overall duration. It would be better to have this
project completed in 24 months, as opposed to 36 months. Given the
pace of industry and academic research attention devoted to this
topic, greater impact would be had if the PIs get their results
sooner.

\subsection*{Reviewer 2}

{\bf Please comment on the objective(s) of the proposal. Could the
research agenda address the objective(s)?}

\vspace{0.5 cm}

Grade:  Good

\vspace{0.5 cm}

    The proposed research is innovative and theoretically interesting.
However, it seems that the PIs lacked the survey on the field of
Internet traffic engineering. As a result, it appears that they did
not address the challenges commonly attacked by the works in TE,
such as robustness against the nonstationarity and unpreditability
of traffic demand.

\vspace{0.5 cm}

{\bf Please comment on the Research Design and Methodology.}

\vspace{0.5 cm}

Grade: Excellent

\vspace{0.5 cm}

    The proposed research plans to develop the traffic engineering method based on the sound queueing
    model with LRD traffic. Besides, the simulation is well planned.

\vspace{0.5 cm}

{\bf Please comment on the feasibility
 of the proposed research. Why?}

\vspace{0.5 cm}

Grade: Good

\vspace{0.5 cm}
    Two following points raise the concern about the feasibility of the proposed research.
First, robustness, which is one of the most important issues in TE,
is not addressed. Second, as the large queue occupation becomes a
rare event, the method based on the queueing model for heavy traffic
could only produce marginal performance gain. However, such concern
are not clarified in the proposal.

Other than aforementioned points, the rest of the proposal,
including flow-size-dependent approach, appears to be feasible.

\vspace{0.5 cm}

{\bf What do you consider to be the most original or innovative
aspect
 of the proposed research? What advances will the research result bring
about to the related field if the proposed research is successful?}

\vspace{0.5 cm}

TE (Traffic Engineering) based on the sound queueing model with LRD
traffic is innovative. Besides, flow-size-dependent TE is original.

\vspace{0.5 cm}

   {\bf Please comment on the reasonableness
 of the proposed budget and manpower planning }

 \vspace{0.5 cm}

Could be reasonable.

\vspace{0.5 cm}

{\bf Overall Comment:}

\vspace{0.5 cm}

 The proposed research is innovative and very
interesting. However, the proposal does not persuade me of the
feasibility of the idea.

\vspace{0.5 cm}

{\bf Strength:}

TE based on the sound queueing model with LRD traffic is innovative.
Besides, flow-size-dependent TE is original.

\vspace{0.5 cm}

{\bf Weaknesses:}

 Concern about the feasibility. Performance gain
could be marginal.

\subsection*{Reviewer 3}

{\bf Please comment on the objective(s) of the proposal. Could the
research agenda address the objective(s)?}

\vspace{0.5 cm}

Grade:  Good

\vspace{0.5 cm}

The objective of achieving energy efficiency in Internet routing is
important and needs to be studied in greater detail. The authors
propose to do this by proposing changes to the current routing
methodology followed in the Interent.

However it is not clear whether the objectives can be met by just
modifying the routing algorithm. A slightly more detailed
description would help in this regard.

\vspace{0.5 cm}

{\bf Please comment on the Research Design and Methodology.}

\vspace{0.5 cm}

Grade: Good

\vspace{0.5 cm}

Lack of sufficient description in research methodology.

\vspace{0.5 cm}

{\bf Please comment on the feasibility
 of the proposed research. Why?}

\vspace{0.5 cm}

Grade: Good

\vspace{0.5 cm}

 Not sufficient information on the proposed methodology to
comment on this.

\vspace{0.5 cm}

{\bf What do you consider to be the most original or innovative
aspect
 of the proposed research? What advances will the research result bring
about to the related field if the proposed research is successful?}

\vspace{0.5 cm}


N/A



\vspace{0.5 cm}

   {\bf Please comment on the reasonableness
 of the proposed budget and manpower planning }

 \vspace{0.5 cm}

N/A

\vspace{0.5 cm}

{\bf Overall Comment:}

\vspace{0.5 cm}

A good proposal with well defined objectives. However the proposal
could have done well by elaborating on the research methodology. The
current description seems too general and takes a well treaded path.

{\bf Strength:}

Well defined objectives

{\bf Weaknesses:}

a) Methodology too general. As a result it is not clear what would
be novel with this proposal as the idea of treating mice and
elephants differently is well known in the literature.
Anything implementable with respect to routing has to be
distributed.
b)  No mention of this key property in the proposal
indicates that the authors do not consider this as a key metric (at
least for this proposal). This should also be one of the important
metrics of the study.

c) A brief description of the optimization problem that is being
solved and the constraints would be helpful for the reviewer to
understand the problem and proposed solution methodology

As a result impact of the research would be low.

\newpage


\bibliographystyle{ieeetran} \bibliography{GRF}

\end{document}
